package LeetCode_Section;

//分离链表
public class DivisionLinked {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            // write code here

            //1、创建两个链表 一大一小
            //2、判断 比x的大小关系
            //3、存放 每存一次创建一个节点
            //4、把大的接入小的
            if (pHead == null || pHead.next == null) {
                return pHead;
            }

            ListNode minNode = null;//存放小的头节点
            ListNode maxNode = null;//存放大的头节点
            ListNode curMin = null;//用来遍历小的
            ListNode curMax = null;//用来遍历大的

            while (pHead != null) {
                if (pHead.val < x) {
                    if (minNode == null) {
                        minNode = pHead;
                        curMin = minNode;
                    }else {
                        curMin.next = pHead;
                        curMin = pHead;
                    }
                }else {
                    if (maxNode == null) {
                        maxNode = pHead;
                        curMax = maxNode;
                    }else {
                        curMax.next = pHead;
                        curMax = pHead;
                    }
                }
                pHead = pHead.next;
            }
            if (minNode == null) {
                return maxNode;
            }
            curMin.next = maxNode;
            if (maxNode != null) {
                curMax.next = null;
            }
            return minNode;
        }
    }
}
